/**
 * 基数排序:把数字产分成一个个位数进行比较排序!
 * 		1. 第一趟按照“个位”分配、收集：得到按照“个位递减”的序列；
 * 		2. 第二趟按照“十位”分配、收集：得到按照“十位递减”的序列，“十位相同”的按照“个位递减”的序列排序；
 * 		3. 第三趟按照“百位”分配、收集：得到按照“百位递减”的序列，“百位相同”的按照“十位递减”的序列排序。
 * 
 * 基数排序按照递减排序的过程如下：
 * 		1. 初始化：设置r个空队列，按照关键字位权重递增的次序（个、十、百），对d个关键字位分别做“分配”和“收集”工作。
 * 		2. 分配：顺序扫描各个元素，若当前处理的关键字为x,则将元素插入Q(x)队列中；
 * 		3. 收集：把Q(r-1), Q(r-2),Q(r-3),Q(r-4),...,Q(0)各个队列中的元素依次入队并链接 
 * 
 * 空间复杂度:需要r个辅助队列，空间复杂度为O(r),r为每一个关键字位有可能取得多少种的取值
 * 时间复杂度:
 * 		算法进行d趟的分配、收集（d表示关键字可以被拆分为几个部分，即是几位数），
 * 		每一趟分配从头到尾把n个元素扫一遍，因此一趟需要O(n)的时间，一趟收集需要r个队列，收集的
 * 		过程是依次扫表这些队列。总的时间复杂度为O(d(n+r))
 * 		平均时间复杂度:O(log2(n))
 * 算法稳定性:稳定的
 * 
 * 堆排序擅长处理：
 * 		1. 数据元素的关键字可以方便的拆分为d组，且d较小。
 * 		2. 每组关键字的取值不大，即r较小。
 * 		3. 数据元素n较大。
 * 
 */

#include <stdio.h>
#include <stdlib.h>

#define bool int
#define true !0
#define false 0

//基数排序基于链式存储实现
typedef struct LinkNode{
	int data;
	struct LinkNode* next;
}LinkNode, *LinkList;

typedef struct LinkQNode{
	LinkNode* front;	//队列的头部指针
	LinkNode* rear;		//队列的尾部指针
}LinkQuene;
//打印
void print(int A[], int n);


int main()
{
	int a[10]={12,43,16,22,63,98,66,90,20,26};
	return 0;
}

void print(int A[], int n)
{
	for(int i=0;i<n;i++)
	{
		printf("%d ",A[i]);
	}
	printf("\n");
}